package leecode

func buildTree(inorder []int, postorder []int) *TreeNode {
	if len(postorder) == 0 || len(inorder) == 0 {
		return nil
	}
	var traversal func(inorder []int, postorder []int) *TreeNode
	traversal = func(inorder []int, postorder []int) (result *TreeNode) {
		if len(postorder) == 0 {
			return
		}
		//后序遍历数组最后一个元素,拿到当前的中间节点
		rootValue := postorder[len(postorder)-1]
		result = &TreeNode{Val: rootValue}
		if len(postorder) == 1 {
			//根节点
			return
		}
		//寻找中序数组的切割点
		var temp int
		for i := 0; i < len(inorder); i++ {
			if inorder[i] == rootValue {
				temp = i
				break
			}
		}
		//切割中序数组
		leftInorder := inorder[:temp]
		rightInorder := inorder[temp+1:]
		//后序数组末尾切割
		postorder = postorder[:len(postorder)-1] //中
		//切割后序数组
		leftPostorder := postorder[:len(leftInorder)]  //左
		rightPostorder := postorder[len(leftInorder):] //右
		//递归
		result.Left = traversal(leftInorder, leftPostorder)
		result.Right = traversal(rightInorder, rightPostorder)
		return result
	}
	return traversal(inorder, postorder)
}
